package jiejie.jianzhioffer;

public class offer13 {
    int m;
    int n;
    int k;
    boolean[][] dp;
    public static void main(String[] args) {

    }

    /**
     * 机器人运动范围
     * @param m
     * @param n
     * @param k
     * @return
     */
    public int movingCount(int m, int n, int k) {
        this.m=m;
        this.n=n;
        this.k=k;
        this.dp=new boolean[m][n];
        return dfs(0,0,0,0);

    }
    public int dfs(int i, int j, int si, int sj){
        if(i>=m || j>=n || si+sj>k || dp[i][j])
            return 0;
        dp[i][j]=true;
        return dfs(i+1,j,si%10==0?si-8:si+1,sj)+dfs(i,j+1,si,sj%10==0?sj-8:sj+1)+1;
    }
}